class Solution {
public:
    int findDuplicate(vector<int>& nums) 
    {
        // 这道题目的解法就是通过，将数组映射为一个链表来进行解决的，
        // 这里我们建立一个映射关系，比如说例子一中的元素,让数组的下标映射值
        // 0->1
        // 1->3
        // 2->4
        // 3->2
        // 4->2
        // 此时去使用下标进行访问首先nums[0] = 1,然后将1当作下标nums[1] = 3，然后将3当作下标
        // nums[3] = 2,nums[2] = 4 nums[4] = 2此时就进入环了，此时就可以转化为判断是否存在环，如果存在环就寻找环的入口
        // 这个入口的元素就是重复的元素,如果寻找呢？首先使用快慢指针，让快慢指针相等的时候结束循环，
        // 然后再从开头指定一个元素开始，让快慢指针相等的地方和开头的元素一起一步一步往前走，当两个元素相等的时候就是重复的元素
        int slow = 0;
        int fast = 0;
        while(true)
        {
            slow = nums[slow];//走一步
            fast = nums[nums[fast]];//走两步
            if(fast == slow)
            {
                break;
            }
        }
        int ret = 0;
        while(ret!=slow)
        {
            ret = nums[ret];
            slow = nums[slow];
        }
        return ret;
    }
};